package com.sise.Linked;

/**
 *      19. 删除链表的倒数第 N 个结点
 *      给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 *      快慢指针问题，同时注意删除的是 头结点的情况，设置哑结点
 */
public class _19_removeNthFromEnd {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 设置哑节点，防止删除的是 头结点而链接不起来
        ListNode pre = new ListNode(0);
        // 将哑节点只想 头结点
        pre.next = head;

        // 设置快慢指针 一开始都指向 哑结点
        ListNode fast = pre;
        ListNode slow = pre;

        // 让快指针先走 n + 1 步，使得它们之间的距离变为 N + 1，所以当 fast == null 时，slow 的下一个节点就是要删除的节点
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // 检查当前节点是否为空，这里的 fast 节点是需求指向空节点的。
        // 由于在内部是 fast = fast.next，所以当 fast 为空时，slow.next 就是要删除的节点
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 改变指向，删除节点
        slow.next = slow.next.next;
        // 最终返回的是 哑结点的下一个节点，可能是头结点；如果头结点被删除，那么就是第二个节点
        return pre.next;
    }
}
